package com.zk.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * O(n^3)
 * O(n^2) + Set
 * O(n^2)
 */
public class Sum3 {

    public static void main(String...args) {
        Utils.println(String.valueOf(new Sum3().threeSum(new int[]{-1,0,1,2,-1,-4})));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        int ai = 0;
        while (ai < nums.length) {
            int a = nums[ai];

            int bi = ai + 1;
            int ci = nums.length - 1;

            while (bi < ci) {
                if (a + nums[bi] + nums[ci] == 0) {
                    List<Integer> r = new ArrayList<Integer>(4);

                    r.add(a);
                    r.add(nums[bi]);
                    r.add(nums[ci]);

                    result.add(r);

                    bi = nextBi(bi, ci, nums);
                    ci = nextCi(bi, ci, nums);
                } else if (a + nums[bi] + nums[ci] > 0) {
                    ci = ci - 1;
                } else {
                    bi = bi + 1;
                }
            }

            ai = nextAi(ai, nums);
        }

        return result;
    }

    private int nextAi(int ai, int[] nums) {
        return nextBi(ai, nums.length, nums);
    }

    private int nextBi(int bi, int ci, int[] nums) {
        while ((bi + 1) < ci && nums[bi + 1] == nums[bi]) {
            bi++;
        }

        bi++;

        return bi;
    }

    private int nextCi(int bi, int ci, int[] nums) {
        while ((ci - 1) > bi && nums[ci - 1] == nums[ci]) {
            ci--;
        }

        ci--;

        return ci;
    }

}
